package momo.multitree.util;

import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;

import momo.multitree.structure.Edge;
import momo.multitree.structure.Graph;
import momo.multitree.structure.Node;
import momo.multitree.structure.Tree;

public class CombinationAlgo implements SpanTreeGenerator
{
	private int mainCounter = 0;
	public double getMin(Graph graph)
	{
		double min = Double.POSITIVE_INFINITY;
		
		if ( graph.isConnectedGraph() )
		{
			Edge[] setOfEdges = graph.getEdges().toArray(new Edge[0]);
			int noOfNodes = graph.getNoOfNodes();
			int[] indices;
			CombinationGenerator gen = new CombinationGenerator (setOfEdges.length, noOfNodes-1);
			Graph g;
			while ( gen.hasMore() )
			{
				g = new Graph();
				indices = gen.getNext();
				for(int i=0; i<indices.length; i++)
					g.add(setOfEdges[indices[i]]);
				if ( g.isConnectedGraph() && !g.hasCycle() )
				{
//					graphs.add(g);
					double currMin = minOfTree(g);
					if ( currMin < min )
						min = currMin;
				}
			}
		}
		return min;
	}
	
	private double minOfTree(Graph g)
	{
		double min = Double.MAX_VALUE;
		
		Set<Node> set = g.getNodes();
		Iterator<Node> iter = set.iterator();
		while ( iter.hasNext() )
		{
			Node root = iter.next();
//			Tree currTree = (Tree.graphToTree(root, g));
			Tree currTree = new Tree(root, g);
			double currMin = currTree.compStability();
			if ( currMin < min )
				min = currMin;
		}
		return min;
	}
	
	public Collection<Tree> enumerateAllSpanningTree(Graph graph)
	{
		return Collections.unmodifiableCollection(convertAllToTrees(generateAllSpanningGraph(graph)));
	}
	
	public Collection<Graph> generateAllSpanningGraph(Graph graph)
	{
		Collection<Graph> graphs = new LinkedHashSet<Graph>();
		int counter = 1;
		int treeCounter = 1;
		if ( graph.isConnectedGraph() )
		{
			Edge[] setOfEdges = graph.getEdges().toArray(new Edge[0]);
			int noOfNodes = graph.getNoOfNodes();
			int[] indices;
			CombinationGenerator gen = new CombinationGenerator (setOfEdges.length, noOfNodes-1);
			Graph g;
			while ( gen.hasMore() )
			{
//				System.out.println("counter: " + (counter++));
				g = new Graph();
				indices = gen.getNext();
				for(int i=0; i<indices.length; i++)
					g.add(setOfEdges[indices[i]]);
				if ( g.isConnectedGraph() && !g.hasCycle() )
				{
					mainCounter ++;
					System.out.println(g.toString());
//					graphs.add(g);
				}
			}
		}
//		System.out.println("Last Tree Count: " + (treeCounter-1));
//		System.out.println("Total Tree in CombiAlgo: " + graphs.size());
		System.out.println(mainCounter);;
		return Collections.unmodifiableCollection(graphs);
	}
	
	private Collection<Tree> convertAllToTrees(Collection<Graph> graphs)
	{
		Collection<Tree> trees = new LinkedHashSet<Tree>();
		Iterator<Graph> iterGraph = graphs.iterator();
		while ( iterGraph.hasNext() )
		{
			Graph g = iterGraph.next();
			Set<Node> set = g.getNodes();
			Iterator<Node> iter = set.iterator();
			while ( iter.hasNext() )
			{
				Node root = iter.next();
//				trees.add(Tree.graphToTree(root, g));
				trees.add(new Tree(root, g));
			}
		}
		return Collections.unmodifiableCollection(trees);
	}
	
}//end of class CombinationAlgo
